//给你一个非负整数数组 nums 和一个整数 target 。 
//
// 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ： 
//
// 
// 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 
// 
//
// 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,1,1,1,1], target = 3
//输出：5
//解释：一共有 5 种方法让最终目标和为 3 。
//-1 + 1 + 1 + 1 + 1 = 3
//+1 - 1 + 1 + 1 + 1 = 3
//+1 + 1 - 1 + 1 + 1 = 3
//+1 + 1 + 1 - 1 + 1 = 3
//+1 + 1 + 1 + 1 - 1 = 3
// 
//
// 示例 2： 
//
// 
//输入：nums = [1], target = 1
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 20 
// 0 <= nums[i] <= 1000 
// 0 <= sum(nums[i]) <= 1000 
// -1000 <= target <= 1000 
// 
//
// Related Topics 数组 动态规划 回溯 👍 1851 👎 0


package com.tyrone.leetcode.editor.cn;


import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class TargetSum {
    public static void main(String[] args) {
        Solution solution = new TargetSum().new Solution();
        System.out.println(solution.findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 动态规划
         *
         * @param nums
         * @param t
         * @return
         */
        public int findTargetSumWays(int[] nums, int t) {
            int s = 0;
            int n = nums.length;
            for (int num : nums) {
                s += num;
            }
            if (t > s || (s - t) % 2 != 0) return 0;
            int nT = (s - t) >> 1;
            int[][] dp = new int[n+1][nT+1]; // dp[i][j]表示 考虑前i个总和为j的方案数
            dp[0][0] = 1;
            //遍历物品数
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <=nT; j++) {
                    //不选
                    dp[i][j] += dp[i-1][j];
                    //选
                    if (j-nums[i-1]>=0)
                    dp[i][j] +=  dp[i-1][j-nums[i-1]];
                }
            }
            return dp[n][nT];
        }

//        /**
//         * 记忆化搜索
//         * @param nums
//         * @param t
//         * @return
//         */
//        public int findTargetSumWays(int[] nums, int t) {
//            return dfs(nums, t, 0, 0);
//        }
//        Map<String, Integer> cache = new HashMap<>();
//        int dfs(int[] nums, int t, int u, int cur) {
//            String key = u + "_" + cur;
//            if (cache.containsKey(key)) return cache.get(key);
//            if (u == nums.length) {
//                cache.put(key, cur == t ? 1 : 0);
//                return cache.get(key);
//            }
//            int left = dfs(nums, t, u + 1, cur + nums[u]);
//            int right = dfs(nums, t, u + 1, cur - nums[u]);
//            cache.put(key, left + right);
//            return cache.get(key);
//        }

        /** dfs暴力搜索
         * @param nums
         * @param target
         * @return
         */
//        public int findTargetSumWays(int[] nums, int target) {
//            return dfs(nums, 0, nums[0], target) + dfs(nums, 0, -nums[0], target);
//        }
//
//        private int dfs(int[] nums, int index, int curr, int target) {
//            if (index + 1 == nums.length) return curr == target ? 1 : 0;
//            int nI = index + 1;
//            return dfs(nums, nI, curr + nums[nI], target) + dfs(nums, nI, curr - nums[nI], target);
//        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}